package com.ShangGuiGu.LinkedList;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.LinkedList;

/**
 * @auther zsj
 * @Date 2021/12/9
 * 对人物的排序，并且实现curd
 * 单列表
 * 单链表---分有头指针和没有头指针的，下面演示有头指针的
 * 每一个节点都有一个data域和一个next域，next指向下一个节点
 **/


public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        HeroNode heroNode1 = new HeroNode(1, "猪猪侠1", "pigMan1");
        HeroNode heroNode2 = new HeroNode(2, "猪猪侠2", "pigMan2");
        HeroNode heroNode3 = new HeroNode(3, "猪猪侠3", "pigMan3");
        HeroNode heroNode4 = new HeroNode(4, "猪猪侠4", "pigMan4");
        //创捷链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(heroNode1);
//        singleLinkedList.add(heroNode2);
//        singleLinkedList.add(heroNode3);
//        singleLinkedList.add(heroNode4);

        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
//        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);





        HeroNode head = singleLinkedList.getHead();
        HeroNode forward = singleLinkedList.forwardIndex(head, 3);
        System.out.println("拿到的节点信息为"+forward);


        int length = getLength(head);
        System.out.println("链表的有效长度为"+length);

//        HeroNode byId = singleLinkedList.getById(2);
//        System.out.println(byId.toString()+"拿到的数据");


//        singleLinkedList.update(new HeroNode(2,"超人强","superman"));
//        singleLinkedList.delete(2);
        //显示链表
        singleLinkedList.list();
    }



    //求出链表中有效的节点个数,在有头节点的时候不算上头节点
    public static int getLength(HeroNode head){
        int length=0;
        if (head.next==null){
            //链表为空
            System.out.println("链表为空");
            return length;
        }
        //不算表头的需要辅助变量
        HeroNode temp = head.next;
        while (temp !=null){
            length++;
            temp=temp.next;
        }
        return length;
    }


}

//定义SingleLinkedList进行所有英雄的管理
class SingleLinkedList {
    //先初始化头节点，头节点不能动
    private HeroNode head = new HeroNode(0, "", "");


    public  HeroNode getHead() {
        return head;
    }

    /**
     * 思路，
     * 1不考虑编号的顺序时，找到当前链表的最后节点
     * 2将最后这个的这个的节点的next域指向为添加的节点
     **/
    //添加节点到单向列表
    public void add(HeroNode node) {
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //当节点的next域为null时就说明这就是最后一个节点
            if (temp.next == null) {
                //找到了
                break;
            }
            //如果没有找到最后
            temp = temp.next;
        }
        //程序执行到这说明，temp已经指向了链表的最后节点
        temp.next = node;
    }

    //第二种添加的方法，可以指定数据的顺序
    public void addByOrder(HeroNode node) {
        //头节点不能动
        HeroNode temp = head;
        //添加的编号是否存在,默认不存在
        boolean flag = false;
        /////////////
        while (true) {
            if (temp.next == null) {
                //说明temp已经在链表最后了
                break;
            }
            //如果temp的编号大于传入的编号，说明传入的编号在temp的后面
            if (temp.next.no > node.no) {
                break;
            } else if (temp.next.no == node.no) {
                flag = true;
                break;
            }
            temp = temp.next;//后移
        }
        /////////////
        if (flag) {
            System.out.printf("编号%d已经存在，无法添加\n", node.no);
        } else {
            //可以添加，temp后面
            //将新节点的next变成原来temp的next,并且把原来的next指向变为添加的数据
            node.next = temp.next;
            temp.next = node;
        }
    }

    //修改节点的信息，根据编号来修改信息，编号不能修改
    public void update(HeroNode newHeroNode){
        if (head.next ==null){
            //说明链表没有节点
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点
        HeroNode temp = head.next;
        boolean flag =false;//是否找到该节点
        while (true){
            if (temp ==null){
                break;//链表到最后一个节点了
            }
            if (temp.no ==newHeroNode.no){
                //找到了
                flag = true;
                break;
            }
            temp=temp.next;//没有找到就往后移动继续找
        }
        if (flag){
            //修改
            temp.name= newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else {
            //没有找到
            System.out.printf("没有找到编号%d的节点，不能修改\n",newHeroNode.no);
        }


    }

    //根据编号来删除节点信息
    public void delete(int no){
        HeroNode temp = head;
        boolean flag=false;//节点中是否含有信息
        while (true){
            if (temp.next ==null){
                //说明节点到最后一个为空
                break;
            }
            if (temp.next.no == no){
                //数据存在
                flag =true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            //修改目标的前一个节点的next域连续跳两个next域就把目标数据给排除了
            //垃圾回收机制会将该数据清除
            temp.next=temp.next.next;
        }else {
            System.out.printf("编号为%d的节点不存在\n",no);
        }
    }

    //根据编号来查找节点信息
    public HeroNode getById(int id){
        HeroNode heroNode= new HeroNode();
        if (head.next ==null){
            //说明链表为空
            System.out.println("链表为空");
            return head;
        }
        boolean flag =false;//表示是否寻找到数据
        HeroNode temp =head.next;
        while (true){
            //遍历
            if (temp.no ==id){
                //找到了
                heroNode.no=id;
                heroNode.name=temp.name;
                heroNode.nickName=temp.nickName;
                heroNode.next=temp.next;
                break;
            }
            temp=temp.next;
        }
        return heroNode;
    }

    //查找单链表中的倒数第k个节点
    public HeroNode forwardIndex(HeroNode head,int k){
        if (head.next==null){
            //说明您这是一个空链表，还找个毛?
            return null;
        }
        //倒数第几个，总数减去k，就是它的位置,需要先拿到所有节点的个数
        int length = SingleLinkedListDemo.getLength(head);
        int index = length -k;
        //校验index是否合法
        if (index <=0 || index > length){
            //不合法
            return null;
        }
        HeroNode node = getById(index+1);
        return node;
    }

    //将单链表进行反转
    public static  void reverseList(HeroNode head){
        if (head.next==null || head.next.next==null){
            //链表为空
            System.out.println("链表为空或只有一个节点，无需反转");
            return;
        }
        //定义辅助指针
        HeroNode cur = head.next;
        //记录一下当前指向的next
        HeroNode next = null;
        //给一个新的链表的表头
        HeroNode reverseHead =new HeroNode(0,"","");
        //遍历原来的链表
        //每遍历一个节点的时候，就将其取出，放在新链表的的next域中
        while (cur !=null){
            //如果链表的next域是空的话，遍历就结束了
            next =cur.next;//将当前链表的next域保存下来
            cur.next = reverseHead.next;//将head.next.next的节点指向新的一个newHead.next的最前端
            reverseHead.next =cur;//将cur连接到新的链表上
            cur = next;//cur后移
        }
        //将head.next指向recerseHead.next,实现单链表的反转
        head.next =reverseHead.next;
    }
    //显示列表(遍历)
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表的最后
            if (temp == null) {
                break;
            }
            //输出节点信息，不为空的情况
            System.out.println(temp);
            //将next后移
            temp = temp.next;
        }
    }


}


//定义英雄属性类，每一个heroNode就是一个节点
@Data
@AllArgsConstructor
@NoArgsConstructor
class HeroNode {
    public int no;//编号
    public String name;//名字
    public String nickName;//绰号
    public HeroNode next;//next指向域

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '}';
    }
}


